public class OPTReplacement {
    //最佳算法
    public static int lackTimes;

    public double replace(int[] pagesSequence, int memoryBlocks){
        //记录缺页次数
        lackTimes = 0;
        //当前页框数
        int[] memory = new int[memoryBlocks];
        //当前的位置
        int curIndex = 0;
        //将所有的内存块置为-1为空闲状态
        for (int i = 0;i<memoryBlocks;i++){
            memory[i]=-1;
        }

        //在内存中寻找页，找到则不操作，没找到则实施替换操作
        for (int i = 0;i<pagesSequence.length;i++){
            if(searchIndex(0,pagesSequence[i],memory)==-1){
                //此时内存块有剩余
                if(memory[memory.length-1] == -1){
                    memory[curIndex] = pagesSequence[i];
                    curIndex++;
                }
                //内存块已满开始记录缺页次数
                else{
                    //记录缺页次数
                    lackTimes++;
                //定义最远使用的块位置
                    int maxIndex = 0;
                    for (int j=0;j<memoryBlocks;j++){
                        //寻找后面第一次使用的位置
                        int index = searchIndex(i+1,memory[j],pagesSequence);
                        //说明后面都没有用到，则直接替换
                        if(index == -1){
                            curIndex = j;
                            break;
                        }
                        //求得最远才使用的位置，并将该内存块定位
                        else{
                            if(maxIndex<index){
                                maxIndex = index;
                                curIndex = j;
                            }
                        }
                    }//for end
                    memory[curIndex] = pagesSequence[i];
                }

            }
        }
        //返回缺页率
        return (lackTimes * 1.0/pagesSequence.length);
    }

    //从startIndex开始，返回最先出现的位置
    public int searchIndex(int startIndex, int page, int[] pagesSquence) {
        for(int i=startIndex;i<pagesSquence.length;i++){
            if(page==pagesSquence[i]){
                return i;
            }
        }
        return -1;
    }
}
